package com.demo.链表.chenglei;

import com.demo.链表.ListNode;
import org.junit.Test;

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author 86130
 */
public class NiuKe {

    @Test
    public void demo4() {
        ListNode list1 = ListNode.getNKLinkedNode(1, 3, 5);
        ListNode list2 = ListNode.getNKLinkedNode(2, 4, 6);
        ListNode.print(list1);
        ListNode.print(list2);
        ListNode.print(demo4_Merge1(list1, list2));

        ListNode list3 = ListNode.getNKLinkedNode(1, 3, 5);
        ListNode list4 = ListNode.getNKLinkedNode(2, 4, 6);
        ListNode.print(demo4_Merge2(list3, list4));
    }

    @Test
    public void demo5() {
        ListNode list5 = ListNode.getNKLinkedNode(-3,-3,-3);
        ListNode list6 = ListNode.getNKLinkedNode(-9,-8,-7,-7,-6,-4,2);
        ListNode list7 = ListNode.getNKLinkedNode(-2,3);
        ListNode list8 = ListNode.getNKLinkedNode(-8,-4,-3,-2);
        ArrayList<ListNode> lists = new ArrayList<>();
        lists.add(list5);
        lists.add(list6);
        lists.add(list7);
        lists.add(list8);
        ListNode[] objs = lists.toArray(new ListNode[lists.size()]);
        ListNode.print(test(objs, 0, objs.length-1));
    }

    @Test
    public void demo12() {
        ListNode head = ListNode.getNKLinkedNode(1,-3,-5, 3, 0);
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        while(head != null) {
            queue.add(head);
            head = head.next;
        }
        ListNode h = null;
        ListNode current = null;
        while(queue.size() > 0) {
            ListNode c = queue.poll();
            if (h == null) {
                h = c;
                current= h;
            } else {
                current.next = c;
                current = c;
            }
        }
        if (current != null) {
            current.next = null;
        }
        ListNode.print(h);
    }

    @Test
    public void demo13() {
        ListNode head = ListNode.getNKLinkedNode(1,3,5, 3, 1, 0);
        Stack<ListNode> stack = new Stack<>();
        ListNode current = head;
        while (current != null) {
            stack.add(current);
            current = current.next;
        }

        while (!stack.empty() && head != null) {
            current = stack.pop();
            if (head.val != current.val ) {
                System.out.println("no");
                return;
            }
            head = head.next;
        }
        System.out.println("yes");
    }

    @Test
    public void demo14 () {
        ListNode head = ListNode.getNKLinkedNode();
        // write code here
        ListNode current = head;
        ListNode ouHead = head.next;
        ListNode ji = null;
        ListNode ou = null;
        boolean flag = true;
        while (current != null) {
            if (flag) {
                if (ji == null) {
                    ji = current;
                } else {
                    ji.next = current;
                    ji = current;
                }
                flag = false;
            } else {
                if (ou == null) {
                    ou = current;
                } else {
                    ou.next = current;
                    ou = current;
                }
                flag = true;
            }
            current = current.next;
        }
        if (ou != null && ou.next != null) {
            ou.next = null;
        }
        if (ouHead != null) {
            ji.next = ouHead;
        }

        ListNode.print(head);
    }

    @Test
    public void demo15 () {
        // write code here
        ListNode head = ListNode.getNKLinkedNode(1,1,1);
        if (head == null) {
            return ;
        }
        Set<Integer> data = new HashSet<>();
        ListNode current = head;
        ListNode nuo = head;
        data.add(head.val);
        while (current != null && current.next != null) {
            current = current.next;
            if (data.contains(current.val)) {
                nuo.next = current.next;
            } else {
                data.add(current.val);
                nuo = current;
            }
        }
        ListNode.print(head);
    }

    @Test
    public void demo16 () {
        // write code here
        ListNode head = ListNode.getNKLinkedNode(1,2,2,3,4,4);
        if (head == null) {
            return ;
        }
        ListNode current = head;
        ListNode nuo = head;
        while (current.next != null) {
            current = current.next;
            if (nuo.val == current.val) {
                nuo.next = current.next;
            } else {
                nuo = current;
            }
        }
        ListNode.print(head);
    }

    @Test
    public void demo17 () {
        int[] arr = new int[]{1, 2, 3, 2, 4, 5, 6};
        int num = 4;
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0 ; i < arr.length; i++) {
            queue.add(arr[i]);
            if (queue.size() == 3) {
                System.out.println(queue.peek());
                queue.remove(arr[i - 2]);
            }
        }
    }

    public ListNode test(ListNode[] objs , int start, int end) {
        if (start == end) {
            return objs[start];
        }
        int mid = start + (end - start) / 2;
        ListNode t1 = test(objs, start, mid);
        ListNode t2 = test(objs, mid+1, end);
        return demo4_Merge1(t1, t2);
    }

    public ListNode merge(ListNode node1, ListNode node2) {
        if (node1 == null || node2 == null) {
            return node1 == null ? node2 : node1;
        }
        if (node1.val <= node2.val) {
            node1.next = merge(node1.next, node2);
            return node1;
        } else  {
            node2.next = merge(node1, node2.next);
            return node2;
        }
    }

    public ListNode demo4_Merge1(ListNode list1,ListNode list2) {
        ListNode head = null;
        ListNode current = null;
        if (list1 == null || list2 == null) {
            return list2 == null ? list1 : list2;
        }
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                if (head == null) {
                    head = list1;
                    current = head;
                } else {
                    current.next = list1;
                    current = list1;
                }
                list1 = list1.next;
            } else {
                if (head == null) {
                    head = list2;
                    current = head;
                } else {
                    current.next = list2;
                    current = list2;
                }
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            current.next = list1;
        }
        if (list2 != null) {
            current.next = list2;
        }
        return head;
    }

    public ListNode demo4_Merge2(ListNode node1, ListNode node2) {
        if (node1 == null || node2 == null) {
            return node1 == null ? node2 : node1;
        }
        if (node1.val <= node2.val) {
            node1.next = demo4_Merge2(node1.next, node2);
            return node1;
        } else  {
            node2.next = demo4_Merge2(node1, node2.next);
            return node2;
        }
    }
}
